Vector quantization as used in the transmission of imagery consists of dividing an image to be transmitted into rectangular blocks, or vectors, of pixels, referred to as the "starting image vectors." A vector quantization system generally comprises a transmitter unit and a receiver unit. The transmitter compares each starting image vector with a large library of typical vectors, called a "codebook," and selects the codebook vector that best approximates the starting image vector. The transmitter then encodes and transmits a codebook index corresponding to the selected codebook vector. The receiver, equipped with a copy of the codebook, decodes the index, retrieves the selected library vector and inserts it into the output image.
Differential vector quantization (DVQ) involves first obtaining a mean value of the starting image vector (referred to as the vector mean or image block mean) by averaging the pixel elements that make up the starting image vector, and rounding the average to the nearest integer. A difference vector is then obtained by subtracting the vector mean from each pixel in the string of pixels that make up the starting image vector. The vector mean is modulated, such as by pulse code modulation (PCM) or by difference pulse code modulation (DPCM), and is transmitted to a companion receiver unit, while the difference vector is used to obtain and transmit a corresponding vector index from the codebook. Normalized differential vector quantization (NDVQ) is DVQ with the codebook vectors normalized such that their magnitudes always equal 1. This method of vector quantization provides higher vector data compression than does DVQ, but requires the separate transmission of the difference vector magnitude.
A newer method of vector quantization is amplitude-adaptive NDVQ, details of which are described, for example, in a publication entitled "Proposal on Component Vector Quantization Coding Scheme" by Mitsubishi Electric Corporation, Annex 4 of CCITT Study Group VIII, Geneva (Dec. 1-12, 1986) (hereinafter "SG VIII"), and in other publications cited therein. In an amplitude-adaptive NDVQ system, a vector mean is subtracted from the pixels of a starting image vector, leaving a difference vector to be quantized. The vector mean is transmitted separately by PCM or DPCM. A binary tree-driven codebook search at the transmitter selects a normalized codebook vector from the codebook library which best correlates with the difference vector, i.e., the codebook vector which together with the difference vector produces the largest dot product. Since the codebook vectors are normalized, this selection is equivalent to minimizing the distance between the two vectors. The dot product is then transmitted by PCM or DPCM, and the index to the selected codebook vector is encoded and transmitted after index correction. Upon receiving this information, the receiver looks up the normalized codebook vector, multiplies it by the dot product and adds the vector mean to form the decoded version of the starting vector. The principal benefit of amplitude-adaptive NDVQ is that, for a given average distortion (square distance between the starting and ending difference vectors), the codebook can be more sparsely populated for small magnitude difference vectors than for large. It might be inferred from SG VIII that the codebook is partitioned by vector magnitude, with small sub-codebooks for small magnitude difference vectors and large sub-codebooks for large magnitude difference vectors. Consequently, it appears that small magnitude difference vectors are assigned short codebook vector index codes, and since small magnitude difference vectors occur much more frequently than large magnitude difference vectors, very high vector data compression can be achieved with good image quality.
However, SG VIII fails to address how to generate an efficient, robust (one that performs well with any image) codebook when there is a specified signal-to-noise ratio goal. The prior art does not appear to have addressed this problem either.